# 背包问题
class Solution:
    def BagProblem(self,weight,value,bag_capacity):
        """
        :param weight: 物品重量
        :param value: 物品价值
        :param bag_capacity: 背包容量
        :return: 背包所能装的最大价值
        """
        nums=len(weight)
        dp=[[0]*(bag_capacity+1) for _ in range(nums)] #创建一个二维数组 (物品数量*背包容量+1)
        for i in range(0,bag_capacity+1):
            if i>=weight[0]:
                dp[0][i]=value[0] #进行第一行初始化，即在背包容量之内将对应填充为物品0的价值
        for i in range(1,nums):
            for capacity in range(1,bag_capacity+1):
                if capacity >= weight[i]: #背包容量大于当前物品重量
                    dp[i][capacity]=max(dp[i-1][capacity],dp[i-1][capacity-weight[i]]+value[i])
                    #dp[i-1][capacity] 背包容量为capacity不放物品i的最大价值
                    #dp[i-1][capacity-weight[i]]+value[i] 放物品i的最大价值
                else:
                    dp[i][capacity]=dp[i-1][capacity]
        return dp[nums-1][bag_capacity]
if __name__=='__main__':
    s=Solution()
    weight=[1,3,4]
    value=[15,20,30]
    bag_capacity=4
    print(s.BagProblem(weight,value,bag_capacity))
